import java.util.Arrays;

public class HashBuck {

    public static void main(String[] args) {
        HashBuck hashBuck = new HashBuck();
        hashBuck.insert(1,110);
        hashBuck.insert(2,112);
        hashBuck.insert(3,113);
        hashBuck.insert(14,111);
        hashBuck.insert(5,111);
        hashBuck.insert(6,111);
        hashBuck.insert(7,111);
        hashBuck.insert(8,111);
        hashBuck.insert(9,111);
        hashBuck.insert(10,11);
        System.out.println();
        System.out.println(hashBuck.get(1));
    }

    /**
     * len表示链长度
     */
    class Node {
        int key;
        int val;
        Node next;

        public Node() {
        }

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    public static final double DEFAULT_LOAD_FACTOR = 0.75;
    public static final int DEFAULT_SIZE = 11;
    public Node[] elem ;
    public int usedSize;

    public HashBuck() {
        this.elem = new Node[DEFAULT_SIZE];
        this.usedSize = 0;
    }

    public void insert (int key, int val) {
        //负载因子>7: 扩容
        if (usedSize / elem.length > 7) {
            grow();
        }

        int index = key % elem.length;
        //
        if (elem[index] != null) {
            Node cur = elem[index];

            while (cur != null) {
                if (cur.val == 0) {
                    cur.val = val;
                    cur.key = key;
                    usedSize++;
                } else {
                    cur = cur.next;
                }
            }

        } else {
            elem[index] = new Node(key, val);
        }
    }

    public void insert (int key, int val, Node[] elem) {
        //负载因子>7: 扩容
        if (usedSize / elem.length > 7) {
            grow();
        }

        int index = key % elem.length;
        //
        if (elem[index] != null) {
            Node cur = elem[index];

            while (cur != null) {
                if (cur.val == 0) {
                    cur.val = val;
                    cur.key = key;
                    usedSize++;
                } else {
                    cur = cur.next;
                }
            }

        } else {
            elem[index].val = val;
            elem[index].key = key;
        }
    }

    public Node[] grow () {

        int len = elem.length;
        //哈希都是二倍扩容?
        Node[] newElem = Arrays.copyOf(elem, len * 2);

        //重新哈希到新数组
        for (int i = 0; i < len; i++) {
            //链表不为空
            if (elem[i] != null) {
                Node cur = elem[i];
                while (cur.next != null) {
                    insert(cur.key, cur.val, newElem);
                    cur = cur.next;
                }
            }
        }

        return newElem;
    }

    public int get (int key) {

        int index = key % elem.length;
        Node cur = elem[index];

        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            } else {
                cur = cur.next;
            }
        }

        return -1;
    }

}
